package basic.courseLearn06.probelm;

import basic.courseLearn06.Utils;
import basic.courseLearn06.TreeNode;
import org.junit.Test;

import java.util.*;

//判断完全二叉树
public class CompleteBinaryTree {

    @Test
    public void test() {
        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

//        root.left.left.left = new TreeNode(5);

        new Utils().treePrint(root);

        System.out.println(isValidCompleteTree(root));
    }


    public boolean isValidCompleteTree(TreeNode root) {
        return solution_1(root);
    }


    /**
     * 解法1：非递归解决：利用层次遍历
     * @param root   根节点
     * @return true：存在，false：不存在
     */
    private boolean solution_1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //1. 根入队
        queue.add(root);
        boolean flag = false;   //flag为true时候，后续节点不可有孩子节点
        //2. 循环，截止条件为队空
        while (!queue.isEmpty()) {   //队列不为空
            //2.1 取出队首节点
            TreeNode node = queue.poll();
            //2.2 分情况讨论
            if (flag){  //后续节点不可有孩子节点
                if (node.left!= null || node.right!= null){
                    return false;
                }
            }else{      //分情况讨论
                if (node.left!=null && node.right!=null){   //左右孩子都不为空，左右孩子入队
                    queue.add(node.left);
                    queue.add(node.right);
                }else if (node.left==null &&node.left==null){    //左孩子为空，右孩子为空，修改flag
                    flag = true;
                }else if (node.left!=null &&node.right==null){    //右孩子为空，左孩子不为空，修改flag，将左孩子入队
                    queue.add(node.left);
                    flag = true;
                }else{      //左孩子为空，右孩子不为空，return
                    return false;
                }
            }

        }
        return true;
    }



}
